CRC calculations are a fundamental part of data transfer in almost all networks, such as the Internet or wireless networks. CRC calculation represents a significant amount of the work required to process all types of data communications. The basic idea of CRC algorithms is simply to treat a message as an enormous binary number, to divide it by another fixed binary number, and to make the remainder from this division the checksum. The checksum is transmitted along with the message. Upon receipt of the message, a receiver can perform the same division and compare the remainder with the checksum. If the computed remainder is the same, then the conclusion is made that the message was properly received.
The division employed in CRC algorithms is not conventional division. Rather it is division derived from binary arithmetic without carries in which addition and subtraction are equivalent and are each equivalent to the XOR operation. A division operation is defined that is consistent with these definitions for addition and subtraction, and will be referred to herein as “CRC division”.
CRC calculation involves the selection of a “polynomial” of length W+1 upon which to base the calculation, where W is the width of the polynomial. This is divided using CRC division into the original message augmented by M−1 “0” bits, the so-called augmented message. To implement CRC division, the message is fed through a division register. In all the following examples the message will be considered to be a stream of bytes (each of 8 bits) with bit 7 of each byte being considered to be the most significant bit (MSB). The bit stream formed from these bytes will be the bit stream with the MSB (bit 7) of the first byte first, going down to bit 0 of the first byte; and then the MSB of the second byte and so on.
With this in mind, an implementation of the CRC division can be sketched. For the purposes of example, consider a polynomial with W=4 and the poly=10111. Then, to perform the division, a 4-bit register is used:
To perform the division perform the following:
Load the register with zero bits.
Augment the message by appending W zero bits to the end of it.
While (more message bits)                Begin        Shift the register left by one bit, reading the next bit of the augmented message into register bit position 0.        If (a 1 bit popped out of the register during the shifting step)                    Register=Register XOR Poly.                        End        
The register now contains the remainder. In practice, the IF condition can be tested by testing the top bit of the register before performing the shift.
Because this simple algorithm operates at the bit level, it is rather awkward to code, and inefficient to execute (it has to loop once for each bit), although H/W implementations often use this method. To speed calculations up, algorithms that process the message a byte at a time are commonly used where most of the calculation is pre-computed and assembled into a table. The above algorithm can be reduced to the following where a 32 bit polynomial is assumed, and where a pre-computed table having 256 32-bit values is employed:
While (augmented message is not exhausted)                Begin                    Top=top_byte(Register); {extract top byte in the register as the index into the pre-computed table}            Register=(Register<<24)|next_augmessage_byte; {shift the register left by one byte, reading in a new message byte}            Register=Register XOR precomputed_table[Top];                        End        
Further details of standard CRC processing can be taken from “A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS” by Ross N. Williams hereby incorporated by reference in its entirety, and “A Tutorial on CRC Computations” published in 1988 in IEEE Micro.